#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    bool is_empty(vector<ListNode*> lists){
        for(auto& list: lists){
            if(list != NULL) return false;
        }
        return true;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> min;
        ListNode* ans = new ListNode;
        ListNode* rear = ans;
        for(int i=0; i<lists.size(); ++i){
            if(lists[i] == NULL) continue;
            min.push({lists[i]->val, i});
            lists[i] = lists[i]->next;
        }

        while(!is_empty(lists)){
            ListNode *newNode = new ListNode(min.top().first);
            int idx = min.top().second;
            min.pop();
            if(lists[idx] != NULL){
                min.push({lists[idx]->val, idx});
                lists[idx] = lists[idx]->next;
            }

            rear->next = newNode;
            rear = newNode;
        }

        while(!min.empty()){
            ListNode *newNode = new ListNode(min.top().first);
            min.pop();
            rear->next = newNode;
            rear = newNode;
        }

        ListNode* deleteNode = ans;
        ans = ans->next;
        delete deleteNode;

        return ans;
    }
};

int main(){

}